package hash;

public class HashBuck {
    static class Node{
        public int key;
        public int val;
        public Node next;
        public Node(int key,int val){
            this.key=key;
            this.val=val;
        }
    }
    public Node[] array;
    public int usedSize;//当前存放的数据的个数
    private static final double  DEFAULT_LOAD_FACTOR = 0.75;
    private static final int DEFAULT_SIZE = 8;//默认桶的大小
    public HashBuck(){
        this.array = new Node[DEFAULT_SIZE];
    }

    /**
     * 存放元素
     * @param key
     * @param val
     */
    public void put(int key,int val){
        Node node = new Node(key,val);
        int index=key%array.length;
        //遍历Index下标的链表，查看是否有一样的key,没有头插法，有val值覆盖
        Node cur =array[index];
        while (cur!=null){
            if(cur.key==key){
                cur.val=val;
                return;
            }
            cur=cur.next;
        }
        //说明没有当前key,jdk用的尾插下面用的头插
        node.next=array[index];
        array[index]=node;
        usedSize++;
        //检查当前哈希表中 是否超过了指定的负载因子
        if(loadFactor()>=DEFAULT_LOAD_FACTOR){
            //扩容&同时进行重新哈希
            resize();
        }

    }

    /**
     * 扩容方法，面试问题：哈希表的扩容需要注意什么吗?
     * 需要遍历数据的每一个链表的每个节点，重新哈希到新的哈希表当中
     */
    private void resize(){
        Node[] temp=new Node[2*array.length];
        //遍历原来的数组
        for (int i = 0; i < array.length; i++) {
            //获取到当前链表下标的头节点
            Node cur=array[i];
            //遍历链表的每个节点
            while (cur!=null){
                Node curNext=cur.next;
                int index=cur.key% temp.length;//获取当前key在新的数组当中的位置
                cur.next=temp[index];//cur被改了，用curNext防止后面节点丢失
                temp[index]=cur;
                cur=curNext;
            }
            
        }
        array=temp;
    }
    private double loadFactor(){
        return (usedSize*1.0)/array.length;
    }

    /**
     * 通过key的值获取value的值
     * @param key
     * @return
     */
    public int get(int key){
        int index= key%array.length;
        Node cur = array[index];
        while (cur!=null){
            if(cur.key==key)
                return cur.val;
            cur=cur.next;
        }
        return -1;
    }
}
